/* 8911106 302933981 Ofri Keidar */

/******************************************************************************
* Student Name: Ofri Keidar
* Exercise Name: Ex3
* File Description: Class Graph's interface. The class represents a graph.
* 					The class has 2 private class- Edge-Linked-List and Edge-In-Graph.
* 					The list is used to represent graph's edges.
* 					Unlike class Edge, Edge-In-Graph has references to its nodes
* 					because these nodes are nodes that were copied to the graph,
* 					in other words, an Edge-In-Graph object has reference to
* 					Node-Linked-List's data. Class Graph could not use class Edge-
* 					in order to prevent extra copies of nodes- more data to save
* 					and maintain. The classes Edge-Linked-List and Edge-In-Graph
* 					must be private, otherwise deleting an instance of Node
* 					could cause invalid data in instances of Edge-Linked-List
* 					and Edge-In-Graph because their nodes would have been deleted.
******************************************************************************/

#ifndef GRAPH_H_
#define GRAPH_H_

#include "Edge.h"
#include "NodeLinkedList.h"

class Graph {

private:
	class EdgeInGraph {

	private:
		const Node& m_out; // reference to out-node
		const Node& m_in; // reference to in-node

	public:

		/***************************************************************************************
		 * function name: EdgeInGraph(const Node& nodeOut, const Node& nodeIn)
		 * The Input: Two references to nodes to be linked by new edge
		 * The output: None
		 * The Function operation: Creates a new Edge object which links between two given nodes
		 ***************************************************************************************/
		EdgeInGraph(const Node& nodeOut, const Node& nodeIn);

		/***************************************************************************************
		 * function name: EdgeInGraph(const EdgeInGraph& edgeToCopy)
		 * The Input: Edge to be copied
		 * The output: None
		 * The Function operation: Creates a new Edge object which links between the nodes that
		 * 						   the given edge links
		 ***************************************************************************************/
		EdgeInGraph(const EdgeInGraph& edgeToCopy);

		/***************************************************************************************
		 * function name: ~EdgeInGraph()
		 * The Input: None
		 * The output: None
		 * The Function operation: Destroys Edge object
		 ***************************************************************************************/
		~EdgeInGraph();

		/***************************************************************************************
		 * function name: getNodeOut()
		 * The Input: None
		 * The output: Reference to node origin of edge
		 * The Function operation: Returns out node reference attribute. Method does not change
		 * 					       Edge object.
		 ***************************************************************************************/
		const Node& getNodeOut() const {return m_out;}

		/***************************************************************************************
		 * function name: getNodeIn()
		 * The Input: None
		 * The output: Reference to node destination of edge
		 * The Function operation: Returns in node reference attribute. Method does not change
		 * 					       Edge object.
		 ***************************************************************************************/
		const Node& getNodeIn() const {return m_in;}

		/***************************************************************************************
		 * function name: == (const EdgeInGraph& other) const
		 * The Input: Edge operand to compare with
		 * The output: True if given operand is equal to object
		 * The Function operation: Compares edge's node attributes. Operator does not
		 * 						   change the object
		 ***************************************************************************************/
		bool operator == (const EdgeInGraph& other) const;

		/***************************************************************************************
		 * function name: != (const EdgeInGraph& other) const
		 * The Input: Edge operand to compare with
		 * The output: True if given operand is not equal to object
		 * The Function operation: Compares edge's node attributes. Operator does not
		 * 						   change the object
		 ***************************************************************************************/
		bool operator != (const EdgeInGraph& other) const;

		/***************************************************************************************
		 * function name: < (const EdgeInGraph& other) const
		 * The Input: Edge operand to compare with
		 * The output: True if given operand's out and in nodes' values are bigger than object's
		 * The Function operation: Compares edge's node attributes. Operator does not
		 * 						   change the object
		 ***************************************************************************************/
		bool operator < (const EdgeInGraph& other) const;

		/***************************************************************************************
		 * function name: <= (const EdgeInGraph& other) const
		 * The Input: Edge operand to compare with
		 * The output: True if both edges' out node value is equal and  given operand's in node
		 * 			   value is bigger
		 * The Function operation: Compares edge's node attributes. Operator does not
		 * 						   change the object
		 ***************************************************************************************/
		bool operator <= (const EdgeInGraph& other) const;

		/***************************************************************************************
		 * function name: toString() const
		 * The Input: None
		 * The output: The string: "(out_Node_Value->in_Node_Value)"
		 * The Function operation: Converts edge to a string
		 ***************************************************************************************/
		 const string toString() const;

		/***************************************************************************************
		 * function name: << (ostream &os, const Edge& edgeToPrint)
		 * The Input: Reference to Edge to be printed
		 * The output: ostream reference
		 * The Function operation: Prints edge
		 ***************************************************************************************/
		friend ostream& operator << (ostream &os, const EdgeInGraph& edgeToPrint);
	}; // end of class EdgeInGraph

	class EdgeLinkedList {

	private:
		class ListNode {

			private:
				/***************************************************************************************
				 * function name: Node(const ListNode& listNodeToCopy)
				 * The Input: List node to be copied
				 * The output: None
				 * The Function operation: Empty implementation. In order to make list nodes have reference
				 * 						   to the graph's edges, edge list is copied via graph copy constructor
				 * 					       because edge list does not have access to the graph's nodes
				 ***************************************************************************************/
				ListNode(const ListNode& listNodeToCopy): m_edgeData(listNodeToCopy.m_edgeData) { }

			public:
				EdgeInGraph& m_edgeData; // reference to edge data
				ListNode* m_prevListNode; // pointer to previous node on list
				ListNode* m_nextListNode; // pointer to next node on list

				/***************************************************************************************
				 * function name: Node (EdgeInGraph& edgeData)
				 * The Input: Edge data to be set as data attribute
				 * The output: None
				 * The Function operation: Creates a new node on list pointing to given edge
				 ***************************************************************************************/
				ListNode(EdgeInGraph& edgeData);


				/****************************************************************************************
				 * function name: ~ListNode()
				 * The Input: None
				 * The output: None
				 * The Function operation: Destructs list node object
				 ***************************************************************************************/
				~ListNode();
		}; // end ListNode class

		ListNode* m_headDummy; // pointer to first node on list
		ListNode* m_tailDummy; // pointer to last node on list
		ListNode* m_currNode; // pointer to current node on list, user can change the node it is pointing at and get a pointer to current data

		/***************************************************************************************
		 * function name: EdgeLinkedList(const EdgeLinkedList& listToCopy)
		 * The Input: List to be copied
		 * The output: None
		 * The Function operation: Empty implementation. Edge lists are copied via graph copy
		 * 						   constructor because graph's edges are created with references
		 * 						   to graph's nodes, and edge list does not have access to the
		 * 						   graph's nodes
		 ***************************************************************************************/
		EdgeLinkedList(const EdgeLinkedList& listToCopy) {}

		/***************************************************************************************
		 * function name: findPlace(const Edge& newEdge)
		 * The Input: Reference to edge to add
		 * The output: List node pointer to which the new edge should be linked.
		 * 			   If an edge with new edge's graph nodes already exists, NULL is returned
		 * The Function operation: The method checks if an edge with the new edge's graph nodes
		 * 						   already exists. If no such edge was found, the method
		 * 						   returns a list node pointer which before it new edge will be linked
		 ***************************************************************************************/
		ListNode* findPlace(const EdgeInGraph& newEdge) const;

		/***************************************************************************************
		 * function name: internalAdd(Edge& edgeToAdd, ListNode* before)
		 * The Input: Reference to edge to be added and a pointer to the list node where the
		 * 			  new edge will be linked
		 * The output: None
		 * The Function operation: The method creates a new list node pointing to the new edge
		 * 					       and links the new edge in the given location to the list
		 ***************************************************************************************/
		void internalAdd(EdgeInGraph& edgeToAdd, ListNode* before);

	public:
		/***************************************************************************************
		 * function name: EdgeLinkedList()
		 * The Input: None
		 * The output: None
		 * The Function operation: Creates a new edge linked list
		 ***************************************************************************************/
		EdgeLinkedList();

		/***************************************************************************************
		 * function name: ~EdgeLinkedList()
		 * The Input: None
		 * The output: None
		 * The Function operation: Deletes the edge linked list but not the pointed data
		 ***************************************************************************************/
		~EdgeLinkedList();

		/***************************************************************************************
		 * function name: addNode(const Edge& newEdge)
		 * The Input: Reference to edge to be added
		 * The output: True if edge was added, False is not
		 * The Function operation: If there is already an edge with the new edge's graph nodes,
		 * 						   edge is not added.
		 * 						   Otherwise, it adds the edge and keeps the list sorted- main
		 * 						   sorting by out-nodes' numbers, secondary sorting by in-nodes'
		 * 						   numbers; from lowest number value to highest
		 ***************************************************************************************/
		bool addNode(const EdgeInGraph& newEdge);

		/***************************************************************************************
		 * function name: removeListNode(const EdgeInGraph& edgeDataToRmv)
		 * The Input: Reference to edge data whose list node should be removed
		 * The output: True if removal was successful, False if not
		 * The Function operation: Search for list node that hold given data. If one was found,
		 * 						   it is removed
		 ***************************************************************************************/
		bool removeListNode(const EdgeInGraph& edgeDataToRmv);

		/***************************************************************************************
		 * function name: operator << (ostream &os, const EdgeLinkedList& listToPrint)
		 * The Input: Reference to edge liked list to be printed
		 * The output: ostream reference
		 * The Function operation: Prints graph's edge list
		 ***************************************************************************************/
		friend ostream& operator << (ostream &os, const EdgeLinkedList& listToPrint);

		/***************************************************************************************
		 * function name: searchByKey(const EdgeInGraph& key)
		 * The Input: Edge (in graph) to look for
		 * The output: Pointer to edge that's equal to given key. If no such edge exists,
		 * 			   NULL is returned.
		 * The Function operation: Scans list- if a match is found, a pointer to this edge is
		 * 						   returned. If not, NULL is returned.
		 * 						   Method does not change list object
		 ***************************************************************************************/
		const EdgeInGraph* searchByKey(const EdgeInGraph& key) const;

		/***************************************************************************************
		 * function name: searchByKey(const Node& outNode, const Node inNode)
		 * The Input: Out and in nodes of edge to look for
		 * The output: Pointer to edge whose out and in node are equal to given keys. If no such
		 * 			   edge exists, NULL is returned.
		 * The Function operation: Scans list- if a match is found, a pointer to this edge is
		 * 						   returned. If not, NULL is returned.
		 * 						   Method does not change list object
		 ***************************************************************************************/
		const EdgeInGraph* searchByKey(const Node& outNode, const Node inNode) const;

		/***************************************************************************************
		 * function name: removeEdges(const Node& nodeToRmv)
		 * The Input: Reference to graph node that edges that link it should be removed
		 * The output: None
		 * The Function operation: Removes all edges that have given graph node as out/in node
		 ***************************************************************************************/
		void removeEdges(const Node& nodeToRmv);

		/***************************************************************************************
		 * function name: initializeCurrNode()
		 * The Input: None
		 * The output: None
		 * The Function operation: Sets current node pointer to point at list's head dummy node
		 ***************************************************************************************/
		void initializeCurrNode() {m_currNode = m_headDummy;}

		/***************************************************************************************
		 * function name: incrmntCurrNode()
		 * The Input: None
		 * The output: False if reached list's tail dummy node or if a next list node does
		 * 			   not exist. Otherwise, returns true
		 * The Function operation: Sets current node pointer to point at list's head dummy node
		 ***************************************************************************************/
		bool incrmntCurrNode();

		/***************************************************************************************
		 * function name: getCurrEdge()
		 * The Input: None
		 * The output: Reference to edge data of list node being pointed by current node pointer
		 * The Function operation: Returns edge data attribute of list node being pointed by
		 * 						   current node pointer. Method does not change the object
		 ***************************************************************************************/
		const EdgeInGraph& getCurrEdge() const {return m_currNode->m_edgeData;}

		/***************************************************************************************
		 * function name: operator == (const EdgeLinkedList& listOperand)
		 * The Input: Edge linked list to compare with
		 * The output: True if all edges are equal, False if not
		 * The Function operation: Compares each list's nodes. Method does not change the object
		 ***************************************************************************************/
		bool operator == (const EdgeLinkedList& listOperand) const;
	}; // end of EdgeLinkedList class

	NodeLinkedList* m_nodeList; // pointer to graph's nodes list
	EdgeLinkedList* m_edgeList; // pointer to graph's edges list

	/***************************************************************************************
	 * function name: CopyNewEdges(const Graph& sourceGraph)
	 * The Input: Reference to graph that its edges should be copied
	 * The output: None
	 * The Function operation: Copies to object all given graph's edges that do not appear
	 * 						   in object
	 ***************************************************************************************/
	void CopyNewEdges(const Graph& sourceGraph);

public:

	/***************************************************************************************
	 * function name: Graph()
	 * The Input: None
	 * The output: None
	 * The Function operation: Creates a new Graph object
	 ***************************************************************************************/
	Graph();

	/***************************************************************************************
	 * function name: Graph(const Graph& graphToCopy)
	 * The Input: Graph to be copied
	 * The output: None
	 * The Function operation: Creates a new Graph object whose attributes are the same as
	 * 						   given graph's
	 ***************************************************************************************/
	Graph(const Graph& graphToCopy);

	/***************************************************************************************
	 * function name: ~Graph()
	 * The Input: None
	 * The output: None
	 * The Function operation: Destructs Graph object without deleting pointed data
	 ***************************************************************************************/
	~Graph();

	/***************************************************************************************
	 * function name: operator << (ostream &os, const EdgeInGraph& edgeToPrint)
	 * The Input: Reference to Edge to be printed
	 * The output: ostream reference
	 * The Function operation: Prints graph's edge
	 ***************************************************************************************/
	friend ostream& operator << (ostream &os, const EdgeInGraph& edgeToPrint);

	/***************************************************************************************
	 * function name: operator <<
	 * The Input: Reference to edge-in-graph linked list to be printed
	 * The output: ostream reference
	 * The Function operation: Prints graph's edge list
	 ***************************************************************************************/
	friend ostream& operator << (ostream &os, const EdgeLinkedList& listToPrint);

	/***************************************************************************************
	 * function name: operator << (ostream &os, const Graph& graphToPrint)
	 * The Input: Reference to Graph to be printed
	 * The output: ostream reference
	 * The Function operation: Prints graph
	 ***************************************************************************************/
	friend ostream& operator << (ostream &os, const Graph& graphToPrint);

	/***************************************************************************************
	 * function name: operator >> (istream &is, Graph& graphToSet)
	 * The Input: Reference to istream object and reference to graph to be set
	 * The output: istream reference
	 * The Function operation: Sets given graph's attributes as nodes and edges that appear
	 * 						   in istream input
	 ***************************************************************************************/
	friend istream& operator >> (istream &is, Graph& graphToSet);

	/***************************************************************************************
	 * function name: operator + (const Node& nodeOperand)
	 * The Input: Reference to node operand
	 * The output: Result graph of adding operation
	 * The Function operation: Copies graph object and adds given node operand to the copy,
	 * 					       copy is returned. Method does not change the object
	 ***************************************************************************************/
	const Graph operator+(const Node& nodeOpearand) const;

	/***************************************************************************************
	 * function name: operator + (const Edge& edgeOperand)
	 * The Input: Reference to node operand
	 * The output: Result graph of adding operation
	 * The Function operation: Copies opeartor's activating graph object and adds given edge
	 * 					       operand to the copy, copy is returned.
	 * 					       Method does not change the object
	 ***************************************************************************************/
	const Graph operator+(const Edge& edgeOpearand) const;

	/***************************************************************************************
	 * function name: operator + (const Graph& graphOperand)
	 * The Input: Reference to graph operand
	 * The output: Result graph of adding operation
	 * The Function operation: Copies graph object and adds given graph operand to the copy,
	 * 					       copy is returned. Method does not change the object
	 ***************************************************************************************/
	const Graph operator+(const Graph& graphOpearand) const;

	/***************************************************************************************
	 * function name: operator - (const Node& nodeOperand)
	 * The Input: Reference to graph node operand
	 * The output: Result graph of operation
	 * The Function operation: Copies opeartor's activating graph object and removes given
	 * 					       graph node operand from the copy, copy is returned.
	 * 					       Method does not change the object
	 ***************************************************************************************/
	const Graph operator-(const Node& nodeOpearand) const;

	/***************************************************************************************
	 * function name: operator - (const Edge& edgeOperand)
	 * The Input: Reference to edge operand
	 * The output: Result graph of operation
	 * The Function operation: Copies opeartor's activating graph object and removes given edge
	 * 					       operand from the copy, copy is returned.
	 * 					       Method does not change the object
	 ***************************************************************************************/
	const Graph operator-(const Edge& edgeOpearand) const;

	/***************************************************************************************
	 * function name: operator - (const Graph& graphOperand)
	 * The Input: Reference to graph operand
	 * The output: Result graph of operation
	 * The Function operation: Copies graph object and removes given graph operand from the copy,
	 * 					       copy is returned. Method does not change the object
	 ***************************************************************************************/
	const Graph operator-(const Graph& graphOpearand) const;

	/***************************************************************************************
	 * function name: operator = (const Graph& graphOperand)
	 * The Input: Reference to new graph's value
	 * The output: Reference to graph object after assignment
	 * The Function operation: If given graph is the activating object, reference to the object
	 * 				           is returned. Otherwise, graph's node and edge lists are deleted
	 * 				           and given graph's lists are set as new graph's attributes
	 ***************************************************************************************/
	Graph& operator=(const Graph& graphOperand);

	/***************************************************************************************
	 * function name: operator += (const Node& nodeOperand)
	 * The Input: Reference to node operand
	 * The output: Result graph of adding operation
	 * The Function operation: Adds given node operand to the graph
	 ***************************************************************************************/
	Graph& operator+=(const Node& nodeOpearand);

	/***************************************************************************************
	 * function name: operator += (const Edge& edgeOperand)
	 * The Input: Reference to edge operand
	 * The output: Result graph of adding operation
	 * The Function operation: Adds given edge operand to the graph
	 ***************************************************************************************/
	Graph& operator+=(const Edge& edgeOpearand);

	/***************************************************************************************
	 * function name: operator += (const Graph& graphOperand)
	 * The Input: Reference to graph operand
	 * The output: Result graph of adding operation
	 * The Function operation: Adds given graph operand to the graph
	 ***************************************************************************************/
	Graph& operator+=(const Graph& graphOpearand);

	/***************************************************************************************
	 * function name: operator -= (const Node& nodeOperand)
	 * The Input: Reference to node operand
	 * The output: Result graph of operation
	 * The Function operation: Removes given node operand from the graph
	 ***************************************************************************************/
	Graph& operator-=(const Node& nodeOpearand);

	/***************************************************************************************
	 * function name: operator -= (const Edge& edgeOperand)
	 * The Input: Reference to edge operand
	 * The output: Result graph of operation
	 * The Function operation: Removes given edge operand to the graph
	 ***************************************************************************************/
	Graph& operator-=(const Edge& edgeOpearand);

	/***************************************************************************************
	 * function name: operator -= (const Graph& graphOperand)
	 * The Input: Reference to graph operand
	 * The output: Result graph of operation
	 * The Function operation: Removes given graph operand from the graph
	 ***************************************************************************************/
	Graph& operator-=(const Graph& graphOpearand);

	/***************************************************************************************
	 * function name: operator ++ ()
	 * The Input: None
	 * The output: Reference to the graph object after its nodes' values were incremented
	 * The Function operation: Increments graph's nodes' values in a PREFIX manner
	 ***************************************************************************************/
	Graph& operator++();

	/***************************************************************************************
	 * function name: operator ++ (int)
	 * The Input: None (the int in method's declaration is a dummy argument to differ from perfix)
	 * The output: The graph object before its nodes' values were incremented
	 * The Function operation: Increments graph's nodes' values in a POSTFIX manner
	 ***************************************************************************************/
	const Graph operator++(int);

	/***************************************************************************************
	 * function name: operator -- ()
	 * The Input: None
	 * The output: Reference to the graph object after its nodes' values were decremented
	 * The Function operation: Decrements graph's nodes' values in a PREFIX manner
	 ***************************************************************************************/
	Graph& operator--();

	/***************************************************************************************
	 * function name: operator -- (int)
	 * The Input: None (the int in method's declaration is a dummy argument to differ from perfix)
	 * The output: The graph object before its nodes' values were decremented
	 * The Function operation: Decrements graph's nodes' values in a POSTFIX manner
	 ***************************************************************************************/
	const Graph operator--(int);

	/***************************************************************************************
	 * function name: operator == (const Graph& graphOperand)
	 * The Input: Graph operand to compare with
	 * The output: True if graphs are equal, False if not
	 * The Function operation: Compares both graph's node and edge lists. Graph's are equal
	 * 						   only if both lists are equal. Method does not change the object
	 ***************************************************************************************/
	bool operator == (const Graph& graphOperand) const;

	/***************************************************************************************
	 * function name: operator != (const Graph& graphOperand)
	 * The Input: Graph operand to compare with
	 * The output: True if graphs are not equal, False if they are equal
	 * The Function operation: Compares both graph's node and edge lists. Graph's are not
	 * 					       equal if node or edge lists are not equal. Method does not
	 * 						   change the object
	 ***************************************************************************************/
	bool operator != (const Graph& graphOperand) const;

	/***************************************************************************************
	 * function name: operator && (const Graph& graphOperand)
	 * The Input: Reference to graph operand
	 * The output: Graph with nodes and edges that are common to both operands
	 * The Function operation: Searches nodes and edges that appear in both graphs and returns
	 * 					       a graph with these nodes and edges. Method does not change
	 * 					       the object
	 ***************************************************************************************/
	const Graph operator && (const Graph& graphOperand) const;

	/***************************************************************************************
	 * function name: operator - () const
	 * The Input: None
	 * The output: Completing graph of object
	 * The Function operation: Creates a graph with the same nodes but with all edges that
	 * 						   do not appear in object
	 ***************************************************************************************/
	const Graph operator - () const;

	/***************************************************************************************
	 * function name: operator [] (const int& nodeValue) const
	 * The Input:Node number
	 * The output: String of all edges that have this node as an out node or an empty string
	 * 			   if there is no node holding given number
	 * The Function operation: Scans edge list and if current edge's out node's value
	 * 				           holds given number, the edge's string conversion is concatenated
	 * 				           to the returned string
	 ***************************************************************************************/
	const string operator [] (const int& nodeValue) const;
}; // end of Graph class

#endif
